
// 单链表的结点，每个结点包含数据域和指针域，其实可以理解一个结点就是一个对象，他在内存空间中分配了自己的内存空间
class Node {
    constructor(data) {
        this.data = data
        this.next = null
    }
}

// 链表是无序的，如果要添加或则删除，那么一定要找到位置的前后两个结点，然后进行操作

// 用到的都是真实的位置，不是索引值

// 单链表, 在链表中要记录表中的头结点还有尾结点， 方便查找和定位
class LinkList {
    size = 0 // 链表的长度
    head = null // 链表的头结点
    tail = null // 链表的尾结点  ， 这个head 和 tail 就是变量名只是用他来表示头尾结点，并且始终让他指向头尾结点

    // 尾插法，在链表尾部添加元素
    append(data) {
        const node = new Node(data)
        if (this.size === 0) { // 表示该链表为空
            this.head = node
            this.tail = node
        } else {
            this.tail.next = node  // 这一句执行了一个左查询，会将原tail结点的next指向新的结点
            this.tail = node  // 这一步是将新的 tail 的指向指向新的结点
        }
        this.size++
    }

    // 根据位置添加元素
    insertIndex(index, data) {
        if (index < 0 || index > this.size) return false
        const node = new Node(data)
        if (this.size === 0) { // 没有长度，直接插入
            this.head = node
            this.tail = node
        }
        if (index === 0 || index === 1) { // 在头部插入
            node.next = this.head
            this.head = node
        }
        // 中间结点
        if (index > 1 && index <= this.size) {
            // 需要循环找到需要插入的那个位置，链表是无序的，所以需要找到前后两个结点，通过循环找到需要插入的位置
            let current = this.head // 单链表从头开始找，也可以从尾部开始找
            let previous = null
            for (let i = 1; i < index; i++) {
                previous = current
                current = current.next
            }
            previous.next = node
            node.next = current
        }
        this.size++
        return true
    }

    // 根据位置找到结点
    findIndex(index) {
        if (index > this.size || index <= 0) { // 超出范围
            return 
        }
        if (index > 0 && index <= this.size) {
           let node = this.head
           for (let i = 1; i < index; i++) {
               node = node.next
           }
           return node
        }
    }

    // 删除
    // 删除相关位置的结点
    delIndex(index) {
        if (index <= 0 || index > this.size) return false
        if (index === 1) { // 删除第一个位置的结点
            this.head = this.head.next
        }
        if (index > 1 && index <= this.size) {
            let current = this.head
            let previous = null

            for (let i = 1; i < index; i++) {
                previous = current
                current = current.next
            }
            if (current === this.tail) {
                previous.next = null
                this.tail = previous
            } else {
                previous.next = current.next
            }
        }
        this.size--
        return true
    }

    // 查
    // 链表长度
    getSize() {
        return this.size
    }

    // 链表是否为空
    isEmpty() {
        return this.size === 0 ? true : false
    }

    // 遍历
    print(){
        if (this.size === 0) {
            console.log("空链表");
            return
        }

        let node = this.head
        while(node) {
            console.log(node.data);
            node = node.next
        }
    }
}

const line = new LinkList()

line.append(1)
line.append(2)
line.append(3)
console.log("链表长度为:", line.getSize());
// line.print()
// line.isEmpty()

line.insertIndex(2, 0)
line.print()
console.log("--------");
line.delIndex(3)
console.log("删除后的");
line.print()
console.log('链表长度为:',line.getSize());
line.insertIndex(3, 0)
line.print()
console.log('链表长度为:',line.getSize());
console.log(line.findIndex(3));
console.log(line.findIndex(4));


